Limpel Ziv STAC (LZS) and Deflate are compression protocols based on the Lempel-Ziv algorithm. Compression generally works by finding repeated sequences of data in the prior output sequences. When repeating sequences are found, a description of the repeating sequence can be sent in substitute of a literal representation of the sequence. The sequence can be represented further with symbols that minimize the size of the sequence, such as representing the literal and description of the repeating sequences of data with symbols of varying length, wherein sequences of data that appears more frequently are matched with shorter bit length symbols to minimize their size. Decompression generally works in reverse of compression. During decompression, a stream of symbols representing literal and repeating sequences of data are translated back to its non-coded form and the repeating sequence data are expanded to the original literal representations.
Within the Deflate protocol and the LZS protocol, the description of the repeating sequence is referred to as a string, which consists of length parameter and a distance parameter. In the Deflate protocol, the length parameter is specified to be between 3 to 258 bytes. The distance parameter is specified to be between 1 to 32,767 bytes. If no repeating sequence is found, then a literal, generally expressed as a byte, is sent. In addition to finding repeating sequences, the Deflate protocol utilizes Huffman encoding symbols to represent the literal and repeating sequences of data. The Huffman encoding scheme substitutes frequently appearing strings and literals with smaller numbers of bits; infrequently appearing strings and literals are substituted with larger numbers of bits. The Deflate protocol supports optimally generated Huffman symbols and standardized fixed Huffman symbols. In optimal Huffman encoding, optimally generated Huffman symbols are dynamically generated for the string and literals and an optimal Huffman coded dictionary is created to be provided with the encoded data stream to allow for its translation. In fixed Huffman encoding, the symbols are defined in the standard. Thus, although the encoding may be suboptimal as the bit-length for the symbols are not optimally customized to the frequency distribution of strings and literals, there is a saving in not having to transmit the coded dictionary as with optimal Huffman encoding.
The LZS protocol works similarly to the Deflate protocol. The differences between the LZS protocol and the Deflate protocol are in the search boundaries. For example, the history window for the LZS protocol is 2 kilobytes, but is 32 kilobytes for the Deflate protocol. As a result, the LZS protocol supports a string distances of 1 to 2,047 bytes, whereas the Deflate protocol supports a string distance of 1 to 32,767 bytes. The LZS protocol supports a string length of 2 to infinite bytes, whereas the Deflate protocol supports a string length of 3 to 258 bytes. Another difference between LZS and Deflate is the symbols used to substitute for the string and literal parameters. The LZS protocol utilizes a fixed set of codes defined in the LZS standard, whereas the Deflate protocol utilizes Huffman, optimal and fixed, codes.
The LZS protocol is defined in the American National Standard for Information System ANSI® X3.241-1994, title “Data Compression Method—Adaptive Coding with Sliding Window for Information Interchange.” This document is referenced herein and is incorporated into this Application in its entirety.
The Deflate protocol standard is defined in the Network Working Group Request for Comments 1951, Deflate Compressed Data Format Specification Version 1.3. This document is referenced herein and is incorporated into this Application in its entirety. It should be appreciated that the term “Deflate” generally refers to a compression process and the term “Inflate” refers to the decompression process of a data stream encoded using the Deflate process.
Although the LZS and Deflate protocols are based on the Lempel-Ziv algorithm, due to the differences between the LZS and Deflate protocols, the protocols are generally implemented independently, which increases the size and cost of the compression and decompression systems that implement them. Additionally, string parameters within the LZS and Deflate protocol have overlapping bit-patterns, which requires extra hardware to address. For example, within the Deflate protocol for fixed Huffman codes, at least 5 bits of the length and distance codes overlap.
Since LZS and Deflate protocol have common bit patterns within the defined code standard, such as between length and distance parameters or between string and literal parameters, it is not contemplated that all the search codes will be utilized concurrently.
Combining the hardware generally results in degradation in performance in having the system interrupted in switching between the overlapping string parameters.